package com.leetcode.leetcode2;

import java.util.Arrays;

/**
 * 最长有效括号
 * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
 *
 * 输入：s = ")()())"
 * 输出：4
 * 解释：最长有效括号子串是 "()()"
 *
 * @author luhd
 * @date 2022-11-04
 */
public class Practice32 {

    public static void main(String[] args) {
        String s = ")()())";
        int i = longestValidParentheses(s);
        System.out.println("最长的子串长度为："+i);
    }

    public static int longestValidParentheses(String s) {
        char[] chars = s.toCharArray();
        if (chars.length == 0) {
            return 0;
        }
        Integer[] dp = new Integer[chars.length];
        Arrays.fill(dp, 0);
        int maxValue = 0;
        for (int i = 1; i < chars.length; i++) {
            if (chars[i] == ')') {
                if (chars[i-1] == '(') {
                    dp[i] = 2;
                    if (i>=2) {
                        dp[i] += dp[i-2];
                    }
                } else if(dp[i-1]>0) {
                    if (i-dp[i-1]-1>=0&&chars[i-dp[i-1]-1]=='(') {
                        dp[i] = dp[i-1] +2;
                        if ((i-dp[i-1]-2) >= 0) {
                            dp[i] += dp[i-dp[i-1]-2];
                        }
                    }
                }
            }
            maxValue = Math.max(maxValue,dp[i]);
        }
        return maxValue;
    }
}
